package cn.zhaoyuening.algorithms.queue;

import java.util.*;

/**
 * Created by Buynow on 2017/8/6.
 */
public class MaxWindowValue {
    public static int[] maxValueList(int[] arr, int windowSize) {
        if (windowSize <= 0||arr.length==0) {
            return null;
        }
        int[] maxArr = new int[arr.length - windowSize + 1];

        if (windowSize >= arr.length) {
            int max = Integer.MIN_VALUE;
            for (int i=0;i<windowSize;i++) {
                max = Math.max(arr[i], max);
            }
            maxArr[0] = max;
            return maxArr;
        }

        Queue<Integer> windowQueue = new LinkedList<>();
        Stack<Integer> maxStack = new Stack<>();
        int max = Integer.MIN_VALUE;
        for (int i=0;i<windowSize;i++) {
            windowQueue.add(arr[i]);
            max = Math.max(max, arr[i]);
            maxStack.add(max);
        }
        maxArr[0] = max;
        for (int i=windowSize,j=1;i<arr.length;i++,j++) {
            int tmp = windowQueue.poll();
            if (tmp >= maxStack.peek()) {
                maxStack.pop();
            }
            if (arr[i] >= maxStack.peek()) {
                maxStack.add(arr[i]);
            }
            windowQueue.add(arr[i]);
            maxArr[j] = maxStack.peek();
        }
        return maxArr;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 3, 5, 4, 3, 3, 6, 7};
        int[] maxArr = maxValueList(arr,3);
        System.out.println(Arrays.toString(maxArr));
    }
}
